#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#define maxn 1000
using namespace std;
/**
 *  给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组* output
 *  其中 output[i] 等于 nums 中除 nums[i] 之外其余各*元素的乘积。
 * 
 *  请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 */
class Solution
{
public:
    /**
     *  思路:[a1,a2,...,ai,aj,ak,...,an]
     *  从a1...ai的乘积x从aj...an的乘积 = output[j]
     *  所以维护两个数组productL,productR即可
     *  时间复杂度:O(3n)
     *  空间复杂度:O(2n)
     */ 
    vector<int> productExceptSelf(vector<int> &nums)
    {
        vector<int> output, productLeft, productRight;
        output.resize(nums.size());
        productLeft.resize(nums.size());
        productRight.resize(nums.size());
        for (int l = 0; l < nums.size(); ++l)
        {
            if (l == 0)
                productLeft[l] = 1;
            else
                productLeft[l] = productLeft[l - 1] * nums[l - 1];
        }
        for (int r = nums.size() - 1; r >= 0; r--)
        {
            if (r == nums.size() - 1)
                productRight[r] = 1;
            else
                productRight[r] = productRight[r + 1] * nums[r + 1];
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            output[i] = productRight[i] * productLeft[i];
        }
        return output;
    }
};
int main()
{

    return 0;
};